// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// 求最小生成树的Prim算法
func minCost(points [][]int) (ans int) {
	n := len(points)

	dis := make([]int, n)
	x, y := points[0][0], points[0][1]
	for i := range dis {
		dis[i] = abs(points[i][0]-x) + abs(points[i][1]-y)
	}

	mark := make([]bool, n)
	for {
		chosen, min := -1, 1_000_000_000
		for i := range dis {
			if !mark[i] && dis[i] < min {
				min, chosen = dis[i], i
			}
		}

		if chosen == -1 {
			break
		}

		mark[chosen] = true
		ans += dis[chosen]

		for i := range dis {
			if mark[i] {
				continue
			}

			d := abs(points[i][0]-points[chosen][0]) + abs(points[i][1]-points[chosen][1])
			if dis[i] > d {
				dis[i] = d
			}
		}
	}

	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func main() {
	points := [][]int{{1, 2}, {3, 4}}
	res := minCost(points)
	fmt.Println(res)
}

//$ go run interview8-1.go
//4
